package PrimeNumbers;
/**
 * 质数是指是指一个大于1的自然数，除了1和它自身外，不能被其它自然数整除，被广泛应用于RSA加密算法中，
 *
 * 要求创建一个测试类，完成如下任务：
 * ①写一个递归方法，可以输出0-n之间的所有质数，
 * ②在主方法中调用该方法，输出0-100之间的质数。
 *
 *除了1和它自身外，不能被其他自然数整除的数叫做质数，否则称为合数，规定1既不是质数也不是合数
 * */
public class PrimeNumbers {
    public static void main(String[] args) {
        //②在主方法中调用该方法，输出0-100之间的质数。
        printPrimes(0, 100);
    }

         //①写一个递归方法，可以输出0-n之间的所有质数
    public static void printPrimes(int firstNum, int endNum) {
        if (firstNum <= endNum) {
            if (isPrime(firstNum)) {
                //firstNum
                System.out.println(firstNum);
            }
            //重新递归2 3 5 ...
            printPrimes(firstNum + 1, endNum);
        }
    }

    public static boolean isPrime(int num) {
        //规定1既不是质数也不是合数
        if (num <= 1) {
            return false;
        }
        //Java中的sqrt方法用于计算一个数的平方根
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) {
                //被其他数整除的为合数
                return false;
            }
        }
        return true;
    }
}
